Message encryption has become increasingly necessary to maintain data privacy and integrity when transmitting messages over a computer network. Industry's reliance on computers and data transmission over networks has led to a substantial increase in the use of encryption systems to safeguard messages or data from unauthorized access. Modern encryption systems must account for not only cryptographic security, but physical security of the implementing hardware.
Encryption is the process of transforming a message into a form that is meaningless to everyone except the intended receiver. Cryptography is the science of making this transformation as intricate as possible, so that reversing it without certain key information is difficult, if not impossible.
Encryption algorithms must be invertible transformations so that encrypted messages can be decrypted. All transformations using the encryption algorithm are referred to generally as a "family" of transformations. Within the family of transformations, modem encryption systems use a key or seed which is a parameter which selects a particular transformation from the family of transformations. An important property of encryption algorithms is that unique keys will define unique encrypted messages or ciphertext.
A cryptosystem can be defined as an encryption algorithm, a decryption algorithm and a specific key which produces an unique invertible transformation using the given algorithm. Ideally, a cryptosystem uses the key and the algorithm to produce a flat distribution for all properties of the message to be encrypted, hiding all natural characteristics of the information that make up the message. It should appear to a potential attacker that the message represents random information.
The security of a cryptosystem is directly related to the uncertainty of the attacker in determining the keys used to encrypt the message. Perfect security can be assured if the key is a string of truly random numbers and is as long as the message being encrypted. Such perfect security is known as a "one time pad" if the key is discarded after a single use.
A system is said to be computationally secure if the task of determining the key is computationally infeasible or intractable. A perfectly secure system is useful because the attacker does not have enough information from the ciphertext to determine the key. On the other hand, computationally secure systems are also useful because while the attacker potentially has enough information in the ciphertext to determine the key, he does not have enough time to complete the task.
Computationally secure systems are rated by their resistance to three types of attack, "ciphertext only attack," "known plain text attack," and "chosen plain text attack." In each type of attack, the attacker is given the encryption and decryption algorithms and with this information attempts to decrypt the message. In the ciphertext only attack, the attacker is also given the encrypted message to examine. Any system failing this attack is considered totally insecure. In a known plain text attack, the attacker is given the algorithm, the original unencrypted message and the encrypted message. Cryptosystems which survive this attack are considered reasonably secure. A chosen plain text attack gives the attacker the algorithm, and the ability to encrypt and decrypt any message chosen. The attacker then attempts to derive the key to the encryption algorithm. Cryptosystems which survive this attack are considered to be very secure.
Cryptographically, several encryption schemes are in wide use today, but each is unsatisfactory for several reasons.
The digital encryption system, or DES as it commonly called, has been widely used by industry and the government since 1977. The DES system uses a 56 bit key to encrypt 64 bit data words through a lengthy process of transformations and substitutions. It is also widely acknowledged that the key length is too short for high security. For modern real time encryption applications, DES has fallen out of favor. The DES system has been substantially challenged with modern super computers and is no longer approved for encrypting government messages.
The disadvantages of the DES encryption system are that it is slow and insecure. The complex transformations used by DES require lengthy software programs to be implemented. Additionally, as the length of the message increases, the time to encrypt it under the DES standard grows disproportionally. Obviously, this limitation is undesirable in an cryptographic system.
Dedicated circuits are available which are faster, but so far, they are prohibitively expensive. A second problem with the DES encryption algorithm is that it provides no description of physical security with respect to the encryption key. Therefore, if the physical security of the key is compromised, the robustness the DES encryption algorithm is no protection. A third disadvantage of DES is that it leaves a signature in the encrypted file sufficient to identify that the DES algorithm has been used. A fourth disadvantage of DES is that the computation time to transverse the transformations required to encrypt a large message or data file is substantial The Rivest-Shamir-Adelman (RSA) algorithm is also in wide use. It relies on the receiver giving the sender a "public key" and the encryption algorithm. The sender encrypts the message and sends it to the receiver using the public key and the algorithm. The receiver then can decode the message using a "private key." Only the intended receiver can decode the encrypted message.
The RSA algorithm is asymmetrical, which means that a different key must be used for encrypting and decrypting messages. It uses keys of between 150 and 200 digits long. To invoke the algorithm, RSA requires calculation of a private key derived from the least common multiple of two large prime numbers. The difficulty in breaking and thus the security of the RSA cryptosystem lies in factoring the two prime numbers. This is an example of an intractable but solvable problem.
One disadvantage of the RSA cryptosystem is that its security relies on the determination of two large prime numbers. As available computer speeds increase, the determination of these two prime numbers will become faster. Moreover, there is substantial mathematical research ongoing to determine new prime number factoring algorithms. Therefore the security of the RSA cryptosystem is steadily and predictably decreasing. Most recently a 160 digit key was broken in as little as eight (8) months. Another disadvantage is that the RSA encryption system is very slow when implemented in software. RSA is about 1000 times slower than DES. Additionally, as the length of the encrypted message increases, the encryption time also increases drastically. As with DES, RSA can leave an encryption signature behind in the encrypted file which allows the encrypting algorithm to be identified. Another problem is that the RSA cryptosystem does not address physical security of the required keys.
Chaos theory has been suggested as a basis for cryptosystems. Chaos theory is based on simple deterministic systems that demonstrate random behavior. Some examples of natural phenomenon exhibiting chaotic behavior include atmospheric weather and turbulent water flow. Uncertainties in information about the system, such as errors, become magnified by the nonlinearity of the equations in the system, resulting in unpredictability of the system after a very short time. Chaotic systems, like the Lorentzian system, are absolutely deterministic given an acceptable set of initial conditions. For the same initial conditions, the system produces the same results. So, even if the results are random, they are repeatable for a given set of initial conditions.
U.S. Pat. No. 5,291,555, to Cuomo and Oppenheim discloses an analog electrical circuit which utilizes a system of Lorenz equations which exhibit chaotic behavior. In implementing these equations, a chaotic driver signal u.sub.t is fed into subsystems synchronizing two additional signals v.sub.t and w.sub.t. Additionally, u.sub.t is summed with a data signal m.sub.t. The driver signal u.sub.t is only slightly perturbed by summing with the message m.sub.t and therefore masks the message m.sub.t. The resulting encrypted signal, c.sub.t is transmitted to the receiving station that uses c.sub.t to synchronize the receiver's subsystems to recreate the original driver signal u.sub.t. This driver signal is then subtracted from c.sub.t, with the results being the original message m.sub.t.
Cuomo and Oppenheim have also disclosed a digital encoding methodology (See Cuomo, Oppenheim, and Strogatz, Synchronization of Lorenz Based Chaotic Circuits with Applications to Communications, IEEE Transactions on Circuits and Systems--II, Analog and Digital Signal Processing 40, 10 (October 1993) 626-633; Also see Cuomo and Oppenheim, Circuit Implementation of Synchronized Chaos with Applications to Communications, Physical Letter 71, 1, Jul. 5, 1993, pp. 65-68) that modifies the subsystem of w.sub.t by modifying a constant b by the message stream m.sub.t. The receiver would recognize digital 1's from 0's by the error induced by comparison from a nonencoded driver's signal u.sub.t.
Both Cuomo and Oppenheim disclosures require that identical electrical components be used in the sending and receiving systems. This is a major drawback for a cryptosystem because of the difficulty in such construction on a commercial scale. Additionally, both disclosures teach systems which are slow because they require a great deal of time to synchronize the receiver's components to the transmitter's components; this is especially a problem with the digital application. An additional drawback of the Cuomo and Oppenheim disclosures that each must use a narrow defined set of "tuning parameters" for each equation, which must be identical in both the transmitter and receiving circuits or digital applications.
A second application of chaos theory is disclosed by U.S. Pat. No. 5,048,068 to Bianco and Reed. Bianco discloses the use of a single nonlinear logistic difference equation: EQU x.sub.n+1 =.mu..sub.n x.sub.n (1-x.sub.n)
where .mu. is a tuning parameter between 3.5-4.0 and x.sub.n is a randomly selected number between 0 and 1 which serves as a key. In this invention, the key is multiplied with the fixed tuning parameter .mu.. The resulting value is then iterated in the logistic difference equation to arrive at a chaotic stream of numbers. This chaotic stream of numbers is then compared with a range and a center point. If the iterated results are in the top of the range, they are assigned a digital 1, if they are in the lower half of the range, they are assigned a digital zero. If they are not in the range they are discarded. A domain transformation results, resulting in a stream of 1's and 0's. The stream of 1's and 0's is then added to a binary message to produce an encrypted message.
The Bianco system has several problems. First, it is slow. The logistic difference equation produces a random set of numbers. The numbers may be outside the predetermined range as required by the disclosure. If the number produced by the equation is outside the range, the equation must be reiterated to produce another number. This process must repeat until the equation produces a number within the given range. Sometimes this can require many cycles before a useable number is generated. Second, the logistic difference equation produces a random set of numbers that is statistically weighted toward the top and bottom of the given range; therefore, it leaves a statistical signature which weakens its cryptographic value. Third, the allowable keyspace for the logistic equation is very small, allowing brute force or iterative attacks to become possible. Fourth, no provision is made for assuring that the same key is not used repeatedly. Considering the small allowable keyspace, the same key must be used a number of times. The more often the same key is used, the more the cryptosystem becomes vulnerable to a chosen plaintext attack, thereby reducing its security. Fifth, no provision is made for checking the key to assure that chaotic behavior results from the equation. If the key chosen does not result in chaotic behavior the Bianco system fails entirely.